<?php

require_once "polynomial.php";

print "<style>
    * { font-size: 15px; border-collapse: collapse; }
    div.matrix { border: solid black 1px; display: inline-block; border-radius: 4px; }
    td { padding: 5px 10px; text-align: center; border: solid lightgray 1px; }
    </style><pre>";

// ДОЛГОСРОК
// * Нахождение минимального вектора преобразования (+\-)
// * Каноническая форма (-)
// * Характеристический многочлен, минимальный многочлен и собственные вектора (-)
// * Блочнодиагональная матрица (-)
// * Вторая нормальная форма (-)
// * Первая нормальная форма (-)
// * Жорданова форма (-)
// * Матрица в большой степени (-)

class Matrix 
{
    private $__rows;
    private $__cols;
    private $__matrix = array();

    // Конструктор
    public function __construct(array $matrix) {
        $this->__rows = count($matrix);
        $this->__cols = is_array($matrix[0]) ? count($matrix[0]) : 1;
        foreach ($matrix as $row) {
            $this->__matrix[] = $row;
        }
    }

    // Получение количества строк
    public function count_rows(): int {
        return $this->__rows;
    }

    // Получение количества столбцов
    public function count_columns(): int {
        return $this->__cols;
    }

    // Получение матрицы
    public function get_array(): array {
        return $this->__matrix;
    }

    // Преобразование объекта класса в строку
    public function __toString(): string {
        $printable = "<div class=\"matrix\"><table>";
        foreach ($this->__matrix as $row_index => $row) {
            $printable .= "<tr>";
            if (is_array($row)) {
                foreach ($row as $index => $element) {
                    if (round($element, 10) == -0) $element = 0;
                    $printable .= "<td>".(round($element, 4))."</td>";
                }
            } else $printable .= "<td>".($row)."</td>";
            $printable .= "</tr>";
        }
        return $printable."</table></div>";
    }

    // Сумма матриц
    public function add(Matrix $other): Matrix {
        if ($other->__rows != $this->__rows || $other->__cols != $this->__cols) die("Invalid size!");
        $result = array();
        foreach ($this->__matrix as $row_index => $row) {
            foreach ($row as $index => $element) {
                $result[$row_index][$index] = $element + $other->__matrix[$row_index][$index];
            }
        }
        return new Matrix($result);
    }

    // Разность матриц
    public function diff(Matrix $other): Matrix {
        if ($other->__rows != $this->__rows || $other->__cols != $this->__cols) die("Invalid size!");
        $result = array();
        foreach ($this->__matrix as $row_index => $row) {
            foreach ($row as $index => $element) {
                $result[$row_index][$index] = $element - $other->__matrix[$row_index][$index];
            }
        }
        return new Matrix($result);
    }

    // Умножение на скаляр
    public function multiply_scalar(int $number): Matrix {
        $result = array();
        foreach ($this->__matrix as $row_index => $row) {
            foreach ($row as $index => $element) {
                $result[$row_index][$index] = $element * $number;
            }
        }
        return new Matrix($result);
    }

    // Произведение матриц
    public function multiply(Matrix $other): Matrix {
        if ($this->__cols != $other->__rows) die("Invalid size!");
        $result = array();
        for ($i = 0; $i < $this->__rows; $i++) {
            for($j = 0; $j < $other->__cols; $j++) {
                $sum = 0;
                for ($k = 0; $k < $this->__cols; ++$k) {
                    $sum += $this->__matrix[$i][$k] * $other->__matrix[$k][$j];
                }
                $result[$i][$j] = $sum;
            }
        }
        return new Matrix($result);
    }

    public function multiply_column(Matrix $other): Matrix {
        if ($this->__cols != $other->__rows) die("Invalid size!");
        $result = array();
        for ($i = 0; $i < $this->__rows; $i++) {
            $sum = 0;
            for ($k = 0; $k < $this->__cols; ++$k) {
                $sum += $this->__matrix[$i][$k] * $other->__matrix[$k];
            }
            $result[$i] = $sum;
        }
        return new Matrix($result);
    }

    // Транспонирование
    public function transpose(): Matrix {
        $result = array();
        foreach ($this->__matrix as $index => $row) {
            $result[$index] = array_column($this->__matrix, $index);
        }
        return new Matrix($result);
    }

    // Сериализация матрицы
    public function serialize(): string {
        $result = "";
        foreach ($this->__matrix as $row_index => $row) {
            foreach ($row as $index => $element) {
                $result .= ($index < $this->__cols - 1 ? $element." " : $element);
            }
            $result .= ($row_index < $this->__rows - 1 ? "\n" : "</div>");
        }        
        return $result;
    }

    // Десериализация матрицы
    static public function unserialize(string $data): Matrix {
        $temp = array();
        foreach (explode("\n", $data) as $row_index => $row) {
            foreach (explode(" ", $row) as $index => $element) {
                $temp[$row_index][$index] = $element; 
            }
        }
        $rows = count($temp); $cols = count($temp[0]);
        foreach ($temp as $row) {
            if (count($row) != $cols) die ("Invalid size!");
        }
        $result = new Matrix($rows, $cols);
        foreach ($temp as $row_index => $row) {
            foreach ($row as $index => $element) {
                $result->__matrix[$row_index][$index] = (int)$element;
            }
        }
        return $result;
    }

    // Чтение неопределённого количества матриц из файла
    public static function get_data(string $fileName): array {
        foreach (explode("***", file_get_contents($fileName)) as $element) {
            $result[] = self::unserialize(trim($element));
        }
        return $result;
    }

    // Приведение матрицы к верхнетреугольному виду
    public function upper_triangle_form(): Matrix {
        $result = clone $this;
        $stair_rows_index = $stair_cols_index = 0;
        while ($stair_rows_index < $result->__rows && $stair_cols_index < $result->__cols) { // Перемещение по главной диагонали
            $result->__matrix = $result->sort_rows($stair_rows_index, $stair_cols_index);
            if ($result->__matrix[$stair_rows_index][$stair_cols_index] == 0) { // Смещение по столбцам
                ++$stair_cols_index;
            } else {
                for ($j = $stair_rows_index + 1; $j < $result->__rows; $j++) { // Вычитание строк
                    $coeff = $result->__matrix[$j][$stair_cols_index] / $result->__matrix[$stair_rows_index][$stair_cols_index];
                    foreach ($result->__matrix[$stair_rows_index] as $index => $element) {
                        $result->__matrix[$j][$index] = $result->__matrix[$j][$index] - $element * $coeff;
                    }
                }
                ++$stair_rows_index; ++$stair_cols_index; // Сдвиг по диагонали
            }
        }
        return $result;
    }

    // Приведение матрицы к специально стпупенчатому виду
    public function row_echelon_form(): Matrix {
        $result = clone $this->upper_triangle_form(); // Приведение матрицы к верхнетреугольному виду
        $stair_rows_index = $stair_cols_index = 0;
        while ($stair_rows_index < $result->__rows && $stair_cols_index < $result->__cols) { // Делаем единицы на каждой ступеньке
            if ($result->__matrix[$stair_rows_index][$stair_cols_index] == 0) {
                ++$stair_cols_index;
            } else {
                $coeff = $result->__matrix[$stair_rows_index][$stair_cols_index];
                for ($j = $stair_rows_index; $j < $this->__cols; $j++) {
                    $result->__matrix[$stair_rows_index][$j] /= $coeff;
                }
                ++$stair_rows_index; ++$stair_cols_index;
            }
        } 
        $position = $result->__rows - 1;
        while ($stair_rows_index > 0 && $stair_cols_index > 0) { // Вычитание из вышестоящих строк
            $temp = $result->get_nearest_stair_index($position); // Нахождение ступеньки
            $stair_rows_index = $temp !== false ? $temp[0] : 0;
            $stair_cols_index = $temp !== false ? $temp[1] : 0;
    
            for ($j = $stair_rows_index - 1; $j >= 0; $j--) {
                if ($result->__matrix[$j][$stair_cols_index] == 0) continue;
                $coeff = $result->__matrix[$j][$stair_cols_index];
                for ($k = $stair_cols_index; $k < $result->__cols; $k++) {
                    $result->__matrix[$j][$k] -= $result->__matrix[$stair_rows_index][$k] * $coeff;
                }
            }
            $position = $stair_rows_index - 1;
        }
        return $result;
    }

    // Нахождение определителя матрицы
    public function determinant(): int {
        if ($this->__rows != $this->__cols) die("Invalid size!");
        $result = 1;
        $row_echelon_form_matrix = $this->upper_triangle_form()->__matrix;
        foreach($row_echelon_form_matrix as $index => $row) {
            $result *= $row_echelon_form_matrix[$index][$index];
        }
        return $result;
    }

    // Приписывание матрицы справа
    public function matrix_merge(Matrix $other): Matrix {
        if ($this->__rows != $other->__rows) die("Invalid size!");
        $result = array();
        foreach ($this->__matrix as $row_index => $row) {
            $result[] = array_merge($row, $other->__matrix[$row_index]);
        }
        return new Matrix($result);
    }

    // TODO: ОТКОРРЕКТИРОВАТЬ ДАННЫЙ МЕТОД
    // Приписывание к матрице столбца справа
    public function column_merge(Matrix $other): Matrix {
        if ($this->__rows != $other->__rows) die("Invalid size!");
        $result = clone $this;
        foreach ($this->__matrix as $row_index => $row) {
            if (is_array($result->__matrix[$row_index])) {
                $result->__matrix[$row_index][] = $other->__matrix[$row_index];
            } else {
                $result->__matrix[$row_index] = [$result->__matrix[$row_index], $other->__matrix[$row_index]];
            }
        }
        return new Matrix($result->__matrix);
    }

    // Получение единичной матрицы соотвтствующего размера
    public function identity_matrix(): Matrix {
        if ($this->__rows != $this->__cols) die("Invalid size!");
        $result = array();
        for ($i = 0; $i < $this->__rows; ++$i) {
            for ($j = 0; $j < $this->__rows; ++$j) {
                $result[$i][$j] = $i == $j ? 1 : 0;
            }
        }
        return new Matrix($result);
    }

    // Нахождение обратной матрицы
    public function inverse(): Matrix {
        foreach ($this->matrix_merge($this->identity_matrix())->row_echelon_form()->__matrix as $row_index => $row) {
            $result[$row_index] = array_slice($row, $this->__cols);
        }
        return new Matrix($result);
    }

    // Перенос нулевых строк в конец
    private function sort_rows($rows_index, $cols_index): array {
        $temp = $zero = array();
        for ($i = $rows_index; $i < $this->__rows; ++$i) {
            if ($this->__matrix[$i][$cols_index] != 0) {
                $temp[] = $this->__matrix[$i];
            }
            else $zero[] = $this->__matrix[$i];
        }
        return array_merge(array_slice($this->__matrix, 0, $rows_index), $temp, $zero);
    }

    // Получение позиции ближайшей ступеньки
    private function get_nearest_stair_index(int $row_index): array {
        for ($i = $row_index; $i >= 0; $i--) {
            foreach ($this->__matrix[$i] as $index => $element) {
                if ($element != 0) return array($row_index, $index);
            }
        }
        return false;
    }

    // TODO: ПЕРВАЯ И ЧЕТВЁРТАЯ МАТРИЦЫ НЕ ПРАВИЛЬНО ПОСЧИТАНЫ
    // Нахождение минимального многочлена преобразования
    public function find_minimal_polynomial(): Polynomial {
        //$timer = new Timer();
        if ($this->__rows != $this->__cols) die("Invalid size!");
        $identity_matrix = $this->identity_matrix();
        $return = array();
        for ($j = 0; $j < $this->__rows; ++$j) {
            $result = $temp = new Matrix(array_column($identity_matrix->__matrix, $j));
            for ($i = 0; $i < $this->__rows; ++$i) {
                $temp = $this->multiply_column($temp);
                $result = $result->column_merge($temp);
            }
            $result = $result->row_echelon_form()->row_echelon_form(); // Эта функция не должна вызываться дважды!
            $coeffs = array_reverse(array_column($result->__matrix, $result->__rows)); // Нахождение минимального многочлена
            $coeffs = array_map(function ($coeff) { return round($coeff, 3) * -1; }, $coeffs);
            $return[] = new Polynomial(array_merge([1], $coeffs));
        }
        return $return[0];
    }
}
